÷ ⚙️ 💻
Systematic Procedures for Efficient Computation
A division algorithm is a systematic procedure for dividing one number (dividend) by another (divisor) to produce a quotient and a remainder.
In computer systems, division must be implemented efficiently in hardware (ALUs, CPUs) or software (compilers, arithmetic libraries).
Implemented in ALUs and CPUs for fast computation
Used in compilers and arithmetic libraries
Almost all division algorithms (binary or decimal) follow these steps:
Load dividend, divisor, quotient, remainder.
Shift dividend/divisor to align significant bits.
Subtract divisor from dividend portion.
If subtraction ≥ 0 → keep result, else restore or adjust.
Set quotient bit (1 or 0) depending on test.
Store updated remainder.
Repeat until all dividend bits are processed.
Basic shift and subtract method
Restores when remainder becomes negative
Avoids restore step, faster
Uses lookup table, modern CPUs
Based on reciprocal approximation
Works like long division in decimal, but with binary numbers (0 and 1). Uses shift and subtract method.
Compare
Subtract
Set Quotient Bit
Bring Down Next Bit
Compare divisor with dividend (or partial dividend).
If divisor ≤ partial dividend → subtract → quotient bit = 1.
Else → quotient bit = 0.
Bring down next bit of dividend and repeat.
📌 Example: Divide 16 ÷ 4 → in binary: 10000 ÷ 100.
Used for signed numbers. If subtraction makes the remainder negative, the original value is restored.
Load dividend & divisor.
Subtract divisor from partial dividend.
If result ≥ 0 → quotient bit = 1.
If result < 0 → restore value (add divisor back), quotient bit = 0.
Shift remainder left and bring down next bit.
Repeat until all bits processed.
Simple and systematic
Slow (extra "restore" step)
Improvement over restoring division. Avoids the restore step → instead adjusts in next iteration.
Subtract
Test Result
Set Quotient Bit
Adjust Next Step
Subtract divisor from partial dividend.
If result ≥ 0 → quotient bit = 1, continue subtracting.
If result < 0 → quotient bit = 0, add divisor in next step (instead of restoring immediately).
At the end, if remainder is negative, perform one correction (add divisor).
Faster than restoring division
Slightly more complex control logic
Used in modern CPUs. Uses a lookup table to decide quotient digits (not just 0 or 1, but also -1, 0, +1).
Lookup Table
Quotient Digit
Operation
Update
Initialize dividend, divisor.
Use lookup table → decide next quotient digit based on remainder/divisor ratio.
Perform subtraction or addition accordingly.
Update quotient and remainder.
Repeat until all bits processed.
Very fast, suitable for floating-point division in processors
Complex hardware design
Based on reciprocal approximation: Instead of directly dividing, it repeatedly multiplies both dividend and divisor by an approximation factor until divisor ≈ 1.
Normalize
Multiply Both
Repeat
Result
Normalize divisor so it approaches 1.
Multiply both dividend & divisor by scaling factors.
Repeat until divisor ≈ 1.
Dividend value → quotient.
Efficient for parallel hardware implementation
Floating-point units (FPUs), GPUs
| Algorithm | Signed? | Speed | Complexity | Used In |
|---|---|---|---|---|
| Binary Division | Unsigned | Slow | Simple | Basic ALUs, teaching |
| Restoring Division | Signed | Moderate | Simple | Early CPUs |
| Non-Restoring Division | Signed | Faster | Moderate | CPUs before SRT |
| SRT Division | Signed | Very Fast | Complex | Modern CPUs, FPUs |
| Goldschmidt Division | Signed | Very Fast | Complex (parallel multipliers needed) | GPUs, floating-point |